import java.util.Arrays;

public class MergeSort {
    /*
    * 时间复杂度：N * log2 N
    * 空间复杂丢：O(N)
    * 稳定性：稳定
    * */
    public static int[] mergeSort(int[] array){
        if(array == null){
            return array;
        }
        mergeSortFunc(array,0,array.length-1);
        return array;
    }
    private static void mergeSortFunc(int[] array,int low,int high){
        if(low >= high){
            return;
        }
//       int mid = (high + low) >>> 1
        int mid = low + ((high - low) >>> 1);
        mergeSortFunc(array,low,mid);// 左边
        mergeSortFunc(array,mid+1,high);// 右边
        merge(array,low,mid,high);
    }

    private static void merge(int[] array,int low,int mid,int high){
        int[] arr = new int[high - low +1];
        int start1 = low;
        int end1 = mid;
        int start2 = mid+1;
        int end2 = high;
        int i = 0;
        while (start1 <= end1 && start2 <= end2){
            if(array[start1] > array[start2]){
                arr[i++] = array[start2++];
            }else{
                arr[i++] = array[start1++];
            }
        }
        while(start1 <= end1){
            arr[i++] = array[start1++];
        }
        while(start2 <= end2){
            arr[i++] = array[start2++];
        }
        for (int j = 0; j < arr.length; j++) {
            array[low++] = arr[j];
        }
    }

/*
* array1 已有序
* array2 已有序
* */
    public static int[] mergeArrays(int[] array1,int[] array2){
        if(array1 == null || array2 == null){
            return array1 == null ? array2: array1;
        }
        int[] arr = new int[array1.length + array2.length];
        int i = 0;// arr 的 遍历变量
        int s1 = 0;//array1 的 遍历变量
        int s2 = 0;//array2 的 遍历变量
        while(s1 < array1.length && s2 < array2.length){
            if(array1[s1] > array2[s2]){
                arr[i++] = array2[s2++];
//                s2++;
//                i++;
            }else{
                arr[i++] = array1[s1++];
//                s1++;
//                i++;
            }
        }
        // 循环结束，有一个数组的元素已经全部存入
        // 接下来就是将另一个数组的元素放入 arr 中
        while (s1 < array1.length){
            arr[i++] = array1[s1++];
//            i++;
//            s1++;
        }
        while (s2 < array2.length){
            arr[i++] = array2[s2++];
//            i++;
//            s2++;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] array = {1,6,7,10,2,3,4,9};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}
